package demo7;

import java.util.Arrays;

/**
 * 快速排序
 */
public class Main4 {
    public static void main(String[] args) {
        int[] arr = {4,1,7,4,9,10,6,6,3,2};
        System.out.println(Arrays.toString(arr));
        quickSort1(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort1(int[] arr,int start,int end){

        // 递归停止条件
        if(start > end) return;;
        //  base中存放基准数
        int base = arr[start];
        int left = start;
        int right = end;

        while(left < right){

            // 顺序很重要，先从右边开始往左找，直到找到比base值小的数
            while(left < right && base <= arr[right]){
                right--;
            }
            arr[left] = arr[right];

            // 再从左往右边找，直到找到比base值大的数
            while(left < right && base >= arr[left]){
                left++;
            }
            arr[right] = arr[left];

        }
        // 基准数归位
        arr[left] = base;

        quickSort1(arr,start,left-1);
        quickSort1(arr,left+1,end);
    }
}
